"""
背包问题

背包问题，有n种物品，每个的种类是wj，价值是vj，背包的重量限制为b，问如何选择物品
使得价值最大？每个物品可取0或多个。

目标函数：

    max sum (vj * xj) for j=1 to n

约束条件：

    sum (wj * xj) for j=1 to n <= b
    xj is natural number

注意：背包问题是比投资问题更难的问题，并且是NP问题，它有动态规划解法，但是复杂度是指数级别的。

状态设计：有两个参数k和y。k表示考虑前k中物品。y表示背包的重量限制为y。
则原问题的解为 dp[n,b]。

状态转移方程：

    dp[k,y]=max{dp[k-1,y], dp[k,y-wk]+vk} k=0,1,...,n; y=0,...,b

解释：对状态k，y，考虑如何把k或者y减少。如果恰好不含有物品k，则得到子问题dp[k-1,y]，
即只考虑前k-1中物品且上限为y。如果含有物品k，则至少含有一件，允许选择的物品范围还是前k个，
但是上限减少了wk。

边界条件：

    dp[0][y]=0
    dp[k][0]=0
    dp[1][y]=y/w1 * v1
    dp[k][y]=-inf, y<0

解释：
1. 表示不考虑任何物品。
2. 上限是0，表示恰好满了。
3. 只考虑物品1，全部都装物品1 。
4. 背包不能装下物品，表示非法状态。

"""


N = 4
B = 10
V = [None, 1, 3, 5, 9]
W = [None, 2, 3, 4, 7]


def DP_Recur(k, y, mem, solution):
    if (k, y) in mem:
        return mem[k, y]
    val = None  # 子问题的解。
    max_id = None  # 子问题k，y用到的最大物品编号。
    if k == 0:
        val = 0
        max_id = 0
    elif y == 0:
        val = 0
        max_id = 0
    elif k == 1:
        val = y // W[k] * V[k]
        max_id = 1
    elif y < 0:
        return -999
    else:
        x1 = DP_Recur(k - 1, y, mem, solution)
        x2 = DP_Recur(k, y - W[k], mem, solution) + V[k]
        if x1 > x2:
            val = x1
            max_id = solution[k - 1, y]  # 和子问题保持不变。
        else:
            val = x2
            max_id = k

    mem[k, y] = val
    solution[k, y] = max_id
    return val


def DP_Iter():
    dp = {}
    solution = {}

    # k=0, 则一切为0
    for y in range(0, B + 1):
        dp[0, y] = 0
        solution[0, y] = 0
    # y=0，则一切为0
    for k in range(0, N + 1):
        dp[k, 0] = 0
        solution[k, 0] = 0
    # k=1，只考虑物品1（都放1）
    for y in range(1, B + 1):
        dp[1, y] = y // W[1] * V[1]
        solution[1, y] = 1

    for k in range(2, N + 1):
        for y in range(1, B + 1):
            x1 = dp[k - 1, y]
            x2 = -999 if y - W[k] < 0 else dp[k, y - W[k]] + V[k]
            if x1 > x2:
                dp[k, y] = x1
                solution[k, y] = solution[k - 1, y]
            else:
                dp[k, y] = x2
                solution[k, y] = k

    result = TrackSolution(solution)
    val = dp[N, B]
    print("dp", dp)
    print("solution", solution)
    print("val", val)
    print("result", result)


def TrackSolution(solution):
    result = [0] * (N + 1)  # 每个物品放了多少。
    y = B  # 上限
    j = N  # 物品
    while solution[j, y]:
        # 放入一个物品j。
        j = solution[j, y]
        # 上限减少。
        y -= W[j]
        # 物品j数量增加。
        result[j] += 1

    result.pop(0)
    return result


def DP_Recur_Solve():
    mem = {}
    solution = {}
    val = DP_Recur(N, B, mem, solution)
    result = TrackSolution(solution)
    print("dp", mem)
    print("solution", solution)
    print("val", val)
    print("result", result)


# DP_Recur_Solve()
DP_Iter()
